<?php
/**
 * 环形链表：表尾指向表头的链表
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbLinkedListInterface;

class CircleLinkedList implements XxbLinkedListInterface
{
    /**
     * @var LinkedListNode|null
     */
    private $head;

    private $size;

    public function __construct()
    {
        $this->size = 0;
        $this->head = null;
    }

    /**
     * 一步创建完链表，并对链表中的结点依次从1开始赋值
     * @param int $capacity
     */
    public function createOrderedList($capacity = 6)
    {
        if ($capacity < 1) {
            throw new \RuntimeException('capacity must egt 1.');
        }

        $this->head = null;
        for ($i=1; $i<=$capacity; $i++) {
            $node = new LinkedListNode($i);
            if (is_null($this->head)) {
                $node->setNext($node);
                $this->head = $node;
            } else {
                $cursor = $this->head;
                while (true) {
                    if ($cursor->getNext() === $this->head) {
                        $cursor->setNext($node);
                        $node->setNext($this->head);
                        break;
                    }
                    $cursor = $cursor->getNext();
                }
            }
        }
    }

    public function __toString()
    {
        $str = 'circle linked list: head [';
        $cursor = $this->head;
        while (!is_null($cursor)) {
            $str .= $cursor->getValue() . '->';
            $cursor = $cursor->getNext();
            if ($cursor === $this->head) {
                $str .= $cursor->getValue();
                break;
            }
        }

        return $str . ']';
    }

    public function isEmpty()
    {
        return $this->size == 0;
    }

    public function add($index, $value)
    {
        // TODO: Implement add() method.
    }

    public function unshift($value)
    {
        // TODO: Implement unshift() method.
    }

    public function push($value)
    {
        // TODO: Implement push() method.
    }

    public function offsetUnset($index)
    {
        // TODO: Implement offsetUnset() method.
    }

    public function pop()
    {
        // TODO: Implement pop() method.
    }

    public function shift()
    {
        // TODO: Implement shift() method.
    }

    public function unsetVal($value)
    {
        // TODO: Implement unsetVal() method.
    }

    public function offsetSet($index, $value)
    {
        // TODO: Implement offsetSet() method.
    }

    public function valueOffsetGet($value)
    {
        // TODO: Implement valueOffsetGet() method.
    }

    public function valueExists($value)
    {
        // TODO: Implement valueExists() method.
    }

    public function offsetGet($index)
    {
        // TODO: Implement offsetGet() method.
    }

    public function bottom()
    {
        // TODO: Implement bottom() method.
    }

    public function top()
    {
        // TODO: Implement top() method.
    }

    public function count()
    {
        // TODO: Implement count() method.
    }

    /**
     * 约瑟夫问题(多人数数游戏)：
     * 多人围成一圈数数，从某个位置开始数数，数到指定的数，当前位置的人就出圈，
     * 接着从下一个位置开始继续数数，直到圈中剩下指定的人数
     * @param int $capacity 结点个数
     * @param int $index 从第几个开始
     * @param int $step 每次数到第几个数
     * @param int $surviveNum 幸存者个数
     */
    public function josephQuestion($capacity = 6, $index = 1, $step = 3, $surviveNum = 1)
    {
        if ($capacity < 1 || $index < 1 || $step < 1 || $surviveNum < 1) {
            throw new \InvalidArgumentException('please set reasonable parameters!');
        }
        if ($index > $capacity) {
            throw new \RuntimeException('index must be less than capacity!');
        }
        if ($step > $capacity) {
            throw new \RuntimeException('step must be less than capacity!');
        }

        $this->createOrderedList($capacity);

        for ($i=1; $i<$index; $i++) {
            // 走到指定的起始点
            $this->head = $this->head->getNext();
        }

        while (true) {
            for ($j=1; $j<$step-1; $j++) {
                $this->head = $this->head->getNext();
            }
            // 输出数中的结点
            echo sprintf("leave node is %d\n", $this->head->getNext()->getValue());
            $this->head->setNext($this->head->getNext()->getNext());
            $this->head = $this->head->getNext();
            $capacity--;
            if ($capacity == $surviveNum) {
                break;
            }
        }
    }
}
